//leetcode 36. Valid Sudoku

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool ifHave(vector<vector<int>>& res, vector<int>& cur)
{
    sort(cur.begin(), cur.end());
    for(int i=0;i<res.size();i++)
    {
        sort(res[i].begin(), res[i].end());
        if(cur==res[i]) return true;
    }
    return false;
}
void backtrack(vector<vector<int>>& res, vector<int>& cur,vector<int>& candidates,int sum,int target)
{
    if(sum==target&&!ifHave(res, cur))
    {
        cout<<sum<<endl;
        res.push_back(cur);
        return;
    }
    for(int i=0;i<candidates.size();i++)
    {
        if(sum+candidates[i]<=target)
        {
            cur.push_back(candidates[i]);
            backtrack(res, cur, candidates, sum+candidates[i], target);
            cur.pop_back();
        }
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(res, cur, candidates, 0, target);
    return res;
}
int main()
{
    vector<int> candidates{2,3,5};
    int target = 8;
    vector<vector<int>> res = combinationSum(candidates, target);
    for(auto &v : res)
    {
        for(auto &i : v) cout << i << " ";
        cout << endl;
    }
    return 0;
}